package org.algorithm.落雪.数组.三月.第四周;

import java.util.Arrays;

/**
 * @author zhx
 * @date 2022-03-21 星期一18:25
 *
 * url: https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class 接雨水 {


    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }

    //按列算
    public static int trap(int[] height) {

        int result = 0;

        int length = height.length;

        for (int i = 1; i < length-1; i++) {

            int max_l = 0,max_r = 0;

            for (int j = i; j >=0 ; j--) {
                //找左侧最大值
                max_l = Math.max(max_l,height[j]);
            }

            if (max_l <= height[i]) {
                continue;
            }

            for (int j = i; j < length; j++) {
                //找右侧最大值
                max_r = Math.max(max_r,height[j]);
            }

            int min = Math.min(max_l, max_r);

            if (min > height[i]) {
                result = result + (min - height[i]);
            }

        }

        return result;
    }

    public static int trap2(int[] height) {

        int result = 0;
        int length = height.length;

        int[] max_l = new int[length];
        int[] max_r = new int[length];

        for (int i = 1; i < length - 1; i++) {
            //它前边的墙的左边的 最高高度 和 它前边的墙的高度 选一个较大的，就是当前列左边最高的墙了
            max_l[i] = Math.max(max_l[i-1],height[i-1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            //它后边的墙的右边的 最高高度 和 它后边的墙的高度 选一个较大的，就是当前列右边最高的墙了
            max_r[i] = Math.max(max_r[i + 1], height[i + 1]);
        }

        for (int i = 0; i < length; i++) {
            int min = Math.min(max_l[i], max_r[i]);
            if (min > height[i]) {
                result = result + (min - height[i]);
            }
        }

        return result;

    }


}
